#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=100000;
const ll maxa=1000000;

class Line {
	public:
		ll v[maxn+2][3], c, now[3], p=0;

		void add(int l, int r, ll tv, ll k) {
			if (c == 0) {
				v[l][0] += k;
				v[r+1][0] -= k;
			} else if (c == 1) {
				v[l][0] += k * tv;
				v[l][1] -= k;
				v[r+1][0]  -= k * tv;
				v[r+1][1] += k;
			} else {
				v[l][0] += k * tv * tv;
				v[l][1] -= 2 * k * tv;
				v[l][2] += k;
				v[r+1][0] -= k * tv * tv;
				v[r+1][1] += 2 * k * tv;
				v[r+1][2] -= k;
			} 
		}

		ll next() {
			p++;
			now[0] += v[p][0];
			now[1] += v[p][1];
			now[2] += v[p][2];
			return p*p*now[2]+p*now[1]+now[0];
		}
};

int check(int n, int a[], int x, int c) {
	static Line e;
	int ret=0;
	ll u = c==0 ? 1 : (c==1 ? x : (ll)x*x);
	memset(e.v, 0, sizeof e.v);
	memset(e.now, 0, sizeof e.now);
	e.c = c, e.p=0;
	for (int i=1; i<=n; i++) {
		int t=(max(a[i]-e.next(), 0LL)+u-1)/u; 
		e.add(i+1, min(i+x, n), i+x, t);
		ret += t;
	}
	return ret;
}

int main() {
	freopen("dispersion.in", "r", stdin);
	freopen("dispersion.out", "w", stdout);

	static int a[maxn+1];
	int num, n, c, k;
	scanf("%d %d %d %d", &num, &n, &c, &k);
	for (int i=1; i<=n; i++) scanf("%d", a+i);

	int ans=-1;
	for (int l=0, r=2*maxa, mid; l<=r; ) {
		mid=(l+r)/2;
		if (check(n, a, mid, c)<=k) {
			ans = mid;
			r = mid-1;
		} else l = mid+1;
	}
	printf("%d\n", ans);

	fclose(stdin);
	fclose(stdout);
	return 0;
}
